package com.hzaupj.sb.util;

import com.google.common.collect.HashBasedTable;
import com.google.common.collect.Table;
import com.hzaupj.sb.vo.Food;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by pengjian_91 on 2015/3/18.
 */
public class BackTracking {

    public Map<String, List<Food>> calc(List<String[]> targetSumList, List<Food> srcFood){
        Map<String, List<Food>> resultList = new HashMap<String, List<Food>>();

        int num = srcFood.size();
        Food[] srcFoodItems = srcFood.toArray(new Food[num]);

        System.out.println("all foodItems:");
        printFoodItems(srcFoodItems);

        int totalSum = sum(srcFoodItems);
        System.out.println("totalSum = " + totalSum);

        String[] targetSumInfo = getTargetSumInfo(totalSum, targetSumList);
        int targetSum = Integer.valueOf(targetSumInfo[0])*10;
        int count =0;
        while (totalSum - targetSum >= 0){
            Food[] answers = getRealAnswer(srcFoodItems, targetSum);
            resultList.put(count+"|"+targetSumInfo[0]+"|"+targetSumInfo[1], coverToList(answers));

            srcFoodItems = delFoodItems(srcFoodItems, answers);
            totalSum = totalSum - sum(answers);

            targetSumInfo = getTargetSumInfo(totalSum, targetSumList);
            targetSum = Integer.valueOf(targetSumInfo[0])*10;
            count++;
        }

        if(srcFoodItems.length > 0){
            resultList.put(count+"|"+targetSumInfo[0]+"|"+targetSumInfo[1], coverToList(srcFoodItems));
        }
        return resultList;
    }

    private String[] getTargetSumInfo(int totalSum, List<String[]> targetSumList) {
        if(targetSumList == null || targetSumList.isEmpty()){
            return new String[]{String.valueOf(totalSum) ,"0"};
        }

        String[] result = null;
        for(String[] strs : targetSumList){
            result = strs;
            int temp = Integer.valueOf(result[0])*10;
            if(totalSum >= temp){
                return result;
            }
        }
        return result;
    }

    private void aaResultList(List<List<Food>> resultList, Food[] srcFoodItems) {
        for(int i=0; i<srcFoodItems.length; i++){
            int temp = i;
            if(i >= resultList.size()){
                temp = i%resultList.size();
            }
            resultList.get(temp).add(srcFoodItems[i]);
        }
    }

    private List<Food> coverToList(Food[] foods){
        List<Food> list = new ArrayList<Food>();
        for(Food food : foods){
            list.add(food);
        }
        return list;
    }

    /**
     * 获取真正的结果
     *
     * 因为有可能返回结果小于targetSum，所以要不断尝试放大targetSum直到大于等于targetSum
     *
     * @param srcFoodItems
     * @param targetSum
     * @return
     */
    private Food[] getRealAnswer(Food[] srcFoodItems, int targetSum) {
        int tempSum = targetSum;
        int srcSum = 0;
        Food[] resultFoodItems = null;
        while (srcSum < targetSum){
            resultFoodItems = getAnswer(srcFoodItems, tempSum);
            srcSum = sum(resultFoodItems);
            tempSum++;
        }

        return resultFoodItems;
    }

    private int sum(Food[] srcFoodItems) {
        int sum = 0;
        for (Food item : srcFoodItems){
            sum += item.getPrice();
        }
        return sum;
    }

    private Food[] delFoodItems(Food[] srcFoodItems, Food[] answers) {
        for (int i=0; i<answers.length; i++){
            for (int j=0; j<srcFoodItems.length; j++){
                if(srcFoodItems[j] == null){
                    continue;
                }
                if(answers[i].getId().equals(srcFoodItems[j].getId())
                        && answers[i].getOwnerNo().equals(srcFoodItems[j].getOwnerNo())){
                    srcFoodItems[j] = null;
                    break;
                }
            }
        }
        List<Food> result = new ArrayList<Food>();
        for (Food srcItem : srcFoodItems){
            if(srcItem == null){
                continue;
            }
            result.add(srcItem);
        }

        return result.toArray(new Food[result.size()]);
    }

    private Food[] getAnswer(Food[] foodItems, int targetSum) {
        Table<Integer,Integer,Integer> foodTable= HashBasedTable.create();
        int i;
        Food food;
        for(i=0; i<=targetSum; i++){
            for(int j=0; j<foodItems.length; j++){
                food = foodItems[j];
                if(food.getPrice() > i){
                    if(j == 0){
                        foodTable.put(j,i,0);
                    }else{
                        foodTable.put(j,i,foodTable.get(j-1,i));
                    }
                }else{
                    int sum =0;
                    if(j == 0){
                        foodTable.put(j,i,food.getPrice());
                        continue;
                    }else{
                        sum = foodTable.get(j-1, i-food.getPrice()) + food.getPrice();
                    }
                    int max = foodTable.get(j-1, i) > sum ? foodTable.get(j-1,i) : sum;
                    foodTable.put(j,i,max);
                }
            }
        }

        List<Food> answers = new ArrayList<Food>();
        int curSum = targetSum;
        for(i=foodItems.length-1;i>=0;i--){
            food = foodItems[i];
            if(curSum == 0){
                break;
            }
            if(i==0 && curSum>0){
                answers.add(food);
                break;
            }
            if(curSum-food.getPrice() < 0){
                continue;
            }
            if(foodTable.get(i,curSum) - foodTable.get(i-1, curSum-food.getPrice()) == food.getPrice()){
                answers.add(food);
                curSum -= food.getPrice();
            }
        }
        return answers.toArray(new Food[answers.size()]);
    }

    private void printFoodTable(Table<Integer, Integer, Integer> foodTable) {
        int rows = foodTable.rowKeySet().size();
        for(int i=0; i<rows; i++){
            Map<Integer, Integer> rowMap = foodTable.row(i);
            System.out.print("[ ");
            int cols = rowMap.keySet().size();
            for(int j=0; j<cols; j++){
                Integer result = rowMap.get(j);
                System.out.print(result + ",");
            }
            System.out.println(" ]");
        }
    }

    private void printFoodItems(Food[] foodItems) {
        for (Food item : foodItems){
            System.out.println(item);
        }
    }
}
